/**
 * 437. 路径总和 III
 * https://leetcode-cn.com/problems/path-sum-iii/
 */
const { createTreeNode } = require('../../libs/public');

/**
 * @param {TreeNode} root
 * @param {number} left
 * @return {number}
 */
function check(root, left) {
  let count = 0;
  if (root.val === left) {
    count += 1;
  }
  if (root.left) {
    count += check(root.left, left - root.val);
  }
  if (root.right) {
    count += check(root.right, left - root.val);
  }
  return count;
}

/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {number}
 */
function traverse(root, target) {
  if (!root) {
    return 0;
  }
  return check(root, target)
    + traverse(root.left, target)
    + traverse(root.right, target);
}

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
function pathSum(root, targetSum) {
  return traverse(root, targetSum);
}

console.log(pathSum(createTreeNode([10, 5, -3, 3, 2, null, 11, 3, -2, null, 1]), 8) === 3);
console.log(pathSum(createTreeNode([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]), 22) === 3);
